package cn.edu.njust.alg.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_113_path_sum_ii {

	public static void ref(TreeNode root, int sum, int pre,
			List<Integer> slist, List<List<Integer>> list) {
		if (root == null) {
			return;
		} else if (root.left == null && root.right == null) {
			if (sum == pre + root.val) {
				slist.add(root.val);
				List<Integer> clist = new ArrayList<Integer>();
				for (int i : slist) {
					clist.add(i);
				}
				list.add(clist);
				slist.remove(slist.size() - 1);
			}
		}
		slist.add(root.val);
		ref(root.left, sum, pre + root.val, slist, list);
		ref(root.right, sum, pre + root.val, slist, list);
		slist.remove(slist.size() - 1);
	}

	public static List<List<Integer>> pathSum(TreeNode root, int sum) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (root == null) {
			return list;
		}
		List<Integer> slist = new ArrayList<Integer>();
		ref(root, sum, 0, slist, list);

		return list;
	}

}
